// STL标准库演示：容器、算法、迭代器
// 编译命令：g++ -o stl_demo stl_demo.cpp

#include <bits/stdc++.h>
using namespace std;

// 容器演示
void containerDemo() {
    cout << "=== STL容器演示 ===" << endl;
    
    // 1. vector - 动态数组
    cout << "\n1. vector (动态数组):" << endl;
    vector<int> vec = {1, 2, 3, 4, 5};
    vec.push_back(6);
    vec.insert(vec.begin() + 2, 10);
    
    cout << "vector内容: ";
    for(int x : vec) {
        cout << x << " ";
    }
    cout << "\n大小: " << vec.size() << ", 容量: " << vec.capacity() << endl;
    
    // 2. list - 双向链表
    cout << "\n2. list (双向链表):" << endl;
    list<string> lst = {"apple", "banana", "cherry"};
    lst.push_front("orange");
    lst.push_back("grape");
    
    cout << "list内容: ";
    for(const string& s : lst) {
        cout << s << " ";
    }
    cout << endl;
    
    // 3. deque - 双端队列
    cout << "\n3. deque (双端队列):" << endl;
    deque<int> dq = {1, 2, 3};
    dq.push_front(0);
    dq.push_back(4);
    
    cout << "deque内容: ";
    for(int x : dq) {
        cout << x << " ";
    }
    cout << endl;
    
    // 4. stack - 栈
    cout << "\n4. stack (栈):" << endl;
    stack<int> st;
    for(int i = 1; i <= 5; i++) {
        st.push(i);
    }
    
    cout << "栈操作 (LIFO): ";
    while(!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
    cout << endl;
    
    // 5. queue - 队列
    cout << "\n5. queue (队列):" << endl;
    queue<int> q;
    for(int i = 1; i <= 5; i++) {
        q.push(i);
    }
    
    cout << "队列操作 (FIFO): ";
    while(!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;
    
    // 6. set - 有序集合
    cout << "\n6. set (有序集合):" << endl;
    set<int> s = {5, 2, 8, 2, 1, 5, 3};
    cout << "set内容 (自动去重和排序): ";
    for(int x : s) {
        cout << x << " ";
    }
    cout << endl;
    
    // 7. map - 有序映射
    cout << "\n7. map (有序映射):" << endl;
    map<string, int> mp;
    mp["Alice"] = 25;
    mp["Bob"] = 30;
    mp["Charlie"] = 35;
    
    cout << "map内容 (按键排序): ";
    for(const auto& pair : mp) {
        cout << pair.first << ":" << pair.second << " ";
    }
    cout << endl;
    
    // 8. unordered_set - 哈希集合
    cout << "\n8. unordered_set (哈希集合):" << endl;
    unordered_set<int> us = {5, 2, 8, 2, 1, 5, 3};
    cout << "unordered_set内容 (去重但无序): ";
    for(int x : us) {
        cout << x << " ";
    }
    cout << endl;
    
    // 9. unordered_map - 哈希映射
    cout << "\n9. unordered_map (哈希映射):" << endl;
    unordered_map<string, int> ump;
    ump["Alice"] = 25;
    ump["Bob"] = 30;
    ump["Charlie"] = 35;
    
    cout << "unordered_map内容 (无序): ";
    for(const auto& pair : ump) {
        cout << pair.first << ":" << pair.second << " ";
    }
    cout << endl;
}

// 算法演示
void algorithmDemo() {
    cout << "\n=== STL算法演示 ===" << endl;
    
    vector<int> numbers = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    cout << "原始数组: ";
    for(int x : numbers) {
        cout << x << " ";
    }
    cout << endl;
    
    // 排序
    sort(numbers.begin(), numbers.end());
    cout << "排序后: ";
    for(int x : numbers) {
        cout << x << " ";
    }
    cout << endl;
    
    // 反转
    reverse(numbers.begin(), numbers.end());
    cout << "反转后: ";
    for(int x : numbers) {
        cout << x << " ";
    }
    cout << endl;
    
    // 查找
    auto it = find(numbers.begin(), numbers.end(), 5);
    if(it != numbers.end()) {
        cout << "找到5，位置: " << distance(numbers.begin(), it) << endl;
    }
    
    // 计数
    int count = count_if(numbers.begin(), numbers.end(), [](int x) {
        return x > 5;
    });
    cout << "大于5的元素个数: " << count << endl;
    
    // 求和
    int sum = accumulate(numbers.begin(), numbers.end(), 0);
    cout << "数组求和: " << sum << endl;
    
    // 最大值和最小值
    auto maxIt = max_element(numbers.begin(), numbers.end());
    auto minIt = min_element(numbers.begin(), numbers.end());
    cout << "最大值: " << *maxIt << ", 最小值: " << *minIt << endl;
    
    // 去重
    sort(numbers.begin(), numbers.end());
    auto uniqueIt = unique(numbers.begin(), numbers.end());
    numbers.erase(uniqueIt, numbers.end());
    cout << "去重后: ";
    for(int x : numbers) {
        cout << x << " ";
    }
    cout << endl;
}

// 迭代器演示
void iteratorDemo() {
    cout << "\n=== 迭代器演示 ===" << endl;
    
    vector<string> words = {"apple", "banana", "cherry", "date", "elderberry"};
    
    // 正向迭代器
    cout << "正向遍历: ";
    for(auto it = words.begin(); it != words.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // 反向迭代器
    cout << "反向遍历: ";
    for(auto it = words.rbegin(); it != words.rend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    // 范围for循环 (C++11)
    cout << "范围for循环: ";
    for(const string& word : words) {
        cout << word << " ";
    }
    cout << endl;
    
    // 迭代器操作
    cout << "\n迭代器操作:" << endl;
    auto it = words.begin();
    cout << "第一个元素: " << *it << endl;
    
    it += 2; // 前进2个位置
    cout << "前进2个位置后: " << *it << endl;
    
    advance(it, -1); // 后退1个位置
    cout << "后退1个位置后: " << *it << endl;
}

// 综合应用：学生成绩统计
void studentGradeDemo() {
    cout << "\n=== 综合应用：学生成绩统计 ===" << endl;
    
    // 学生成绩数据
    map<string, vector<int>> studentGrades;
    studentGrades["Alice"] = {85, 90, 78, 92};
    studentGrades["Bob"] = {76, 82, 88, 85};
    studentGrades["Charlie"] = {92, 88, 95, 90};
    studentGrades["Diana"] = {78, 85, 80, 82};
    
    // 计算每个学生的平均分
    map<string, double> averages;
    for(const auto& student : studentGrades) {
        const vector<int>& grades = student.second;
        double sum = accumulate(grades.begin(), grades.end(), 0.0);
        averages[student.first] = sum / grades.size();
    }
    
    // 按平均分排序
    vector<pair<string, double>> sortedStudents;
    for(const auto& avg : averages) {
        sortedStudents.push_back(avg);
    }
    
    sort(sortedStudents.begin(), sortedStudents.end(), 
         [](const pair<string, double>& a, const pair<string, double>& b) {
             return a.second > b.second;
         });
    
    // 输出结果
    cout << "学生成绩排名:" << endl;
    for(int i = 0; i < sortedStudents.size(); i++) {
        cout << (i + 1) << ". " << sortedStudents[i].first 
             << " - 平均分: " << sortedStudents[i].second << endl;
    }
    
    // 统计所有成绩
    vector<int> allGrades;
    for(const auto& student : studentGrades) {
        for(int grade : student.second) {
            allGrades.push_back(grade);
        }
    }
    
    sort(allGrades.begin(), allGrades.end());
    
    cout << "\n全体成绩统计:" << endl;
    cout << "最高分: " << *max_element(allGrades.begin(), allGrades.end()) << endl;
    cout << "最低分: " << *min_element(allGrades.begin(), allGrades.end()) << endl;
    cout << "平均分: " << accumulate(allGrades.begin(), allGrades.end(), 0.0) / allGrades.size() << endl;
    
    // 成绩分布
    map<string, int> distribution;
    for(int grade : allGrades) {
        if(grade >= 90) distribution["优秀"]++;
        else if(grade >= 80) distribution["良好"]++;
        else if(grade >= 70) distribution["中等"]++;
        else if(grade >= 60) distribution["及格"]++;
        else distribution["不及格"]++;
    }
    
    cout << "\n成绩分布:" << endl;
    for(const auto& dist : distribution) {
        cout << dist.first << ": " << dist.second << "人" << endl;
    }
}

int main() {
    cout << "STL标准库演示" << endl;
    cout << "==============" << endl;
    
    containerDemo();
    algorithmDemo();
    iteratorDemo();
    studentGradeDemo();
    
    return 0;
}
